The invention relates to methods of image processing including those referred to as morphological scale-space transforms or sieves, described in Bangham et al, “Morphological scale-space preserving transforms in many dimensions”, Journal of Electronic Imaging, July 1996, vol 5(3), pp 283-299. A sieve is essentially a method of image segmentation in which the image is divided into cells (maximal connected regions of equal pixel value) and repeated operations are performed to merge cells together to make larger cells, corresponding to objects in the picture. The following paragraphs define terms and describe the sieve operations.
It is usual to consider a single component of a digital image, for example the luminance. A group of pixels is known as a 4-connected region if it is possible to travel between any two pixels in the group by moving between adjacent pixels horizontally or vertically. The techniques described here extend in an obvious manner to 8-connected, 6-connected or other adjacency criteria. Pixels can be regarded as adjacent to appropriately located pixels in a neighbouring image in a sequence of images. A connected region is called a cell if all its pixels have the same value and it is a maximal such group, i.e. no pixel adjoining the cell has the value of the cell's pixels (adjacency of cells is defined in the natural way through adjacency of the cells' pixels; adjacent cells are also called neighbours). Thus, the image can be considered to be a union of cells where neighbouring cells have distinct pixel values. A cell is a maximum cell if its pixel value is greater than that of all its neighbours; likewise, it is a minimum cell if its pixel value is less than that of all its neighbours. Cells that are either maximum cells or minimum cells are referred to as outlying cells. In segmentation applications, maximum and minimum cells are regarded as corresponding with objects in the scene depicted by the image. The size of a cell is simply defined as the number of pixels it contains.
The basic known sieve operator consists of an opening followed by a closing. This is applied successively under the control of a scale value which begins at 1 and increments after each sieve operation. The opening operator only affects pixels in maximum cells whose size is equal to the scale value. It changes them all to be equal to the maximum neighbouring pixel. Likewise, the closing operator only affects pixels in minimum cells whose size is equal to the scale value. It changes them all to be equal to the minimum neighbouring pixel. It follows that the opening operator always expands maximum cells by at least one pixel and the closing operator always expands minimum cells by at least one pixel. Therefore, an opening followed by a closing expands outlying cells by at least one pixel. It follows that after opening and closing with a certain scale, all outlying cells will be bigger than the scale value.
The sieve is formed by applying the opening and closing operators alternately. The picture obtained at each stage is of interest—it looks progressively simpler but edges that do remain do not move or become blurred. The sieve itself consists of the differences between successive pairs of opening and closing operators. Thus, successive elements of the sieve extract successively larger objects from the picture. It also follows that the original picture can be reconstructed by summing all the sieve elements.
The most computationally intensive task in implementing sieves is the opening or closing operator itself. The two operators are equivalent except for changes in the sense of comparisons between pixel values. The need for repeated applications of the opening and closing operators as the scale factor increments, hampers attempts to perform the sieve operation more quickly. It is also unhelpful that the processing speed and memory requirements of known software are picture dependent. It is thus difficult to guarantee real-time processing of, for example video material, unless the processing speed is made extremely fast and a very large amount of high-bandwidth memory is made available.